Everything about Graph Theory totally explained
In
mathematics and
computer science,
graph theory is the study of
graphs: mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of
vertices or 'nodes' and a collection of
edges that connect pairs of vertices. A graph may be
undirected, meaning that there's no distinction between the two vertices associated with each edge, or its edges may be
directed from one vertex to another; see
graph (mathematics) for more detailed definitions and for other variations in the types of graphs that are commonly considered. The graphs studied in graph theory shouldn't be confused with "
graphs of functions" and
other kinds of graphs.
Please refer to
Glossary of graph theory for some basic definitions in graph theory.
History
The paper written by
Leonhard Euler on the
Seven Bridges of Königsberg and published in
1736 is regarded as the first paper in the history of graph theory. This paper, as well as the one written by
Vandermonde on the
knight problem, carried on with the
analysis situs initiated by
Leibniz. Euler's formula relating the number of edges, vertices, and faces of a convex polyhedron was studied and generalized by
Cauchy and
L'Huillier, and is at the origin of
topology.
More than one century after Euler's paper on the bridges of
Königsberg and while
Listing introduced topology,
Cayley was led by the study of particular analytical forms arising from
differential calculus to study a particular class of graphs, the
trees. This study had many implications in theoretical
chemistry. The involved techniques mainly concerned the
enumeration of graphs having particular properties. Enumerative graph theory then rose from the results of Cayley and the fundamental results published by
Pólya between
1935 and
1937 and the generalization of these by
De Bruijn in
1959. Cayley linked his results on trees with the contemporary studies of chemical composition. The fusion of the ideas coming from mathematics with those coming from chemistry is at the origin of a part of the standard terminology of graph theory. In particular, the term
graph was introduced by
Sylvester in a paper published in
1878 in
Nature.
One of the most famous and productive problems of graph theory is the
four color problem: "Is it true that any map drawn in the plane may have its regions colored with four colors, in such a way that any two regions having a common border have different colors?". This problem remained unsolved for more than a century and the proof given by
Kenneth Appel and
Wolfgang Haken in
1976 (determination of 1936 types of configurations of which study is sufficient and checking of the properties of these configurations by computer) didn't convince all the community. A simpler proof considering far fewer configurations was given twenty years later by
Robertson,
Seymour,
Sanders and
Thomas.
This problem was first posed by
Francis Guthrie in
1852 and the first written record of this problem is a letter of
De Morgan addressed to
Hamilton the same year. Many incorrect proofs have been proposed, including those by Cayley,
Kempe, and others.
The study and the generalization of this problem by
Tait,
Heawood,
Ramsey and
Hadwiger has in particular led to the study of the colorings of the graphs embedded on surfaces with arbitrary
genus. Tait's reformulation generated a new class of problems, the
factorization problems, particularly studied by
Petersen and
Kőnig. The works of Ramsey on colorations and more specially the results obtained by
Turán in
1941 is at the origin of another branch of graph theory, the
extremal graph theory.
The autonomous development of topology from
1860 and
1930 fertilized graph theory back through the works of
Jordan,
Kuratowski and
Whitney. Another important factor of common development of graph theory and topology came from the use of the techniques of modern algebra. The first example of such a use comes from the work of the physicist
Gustav Kirchhoff, who published in
1845 his
Kirchhoff's circuit laws for calculating the
voltage and
current in
electric circuits.
The introduction of probabilistic methods in graph theory, especially in the study of
Erdős and
Rényi of the asymptotic probability of graph connectivity, gave rise to yet another branch, known as
random graph theory, which has been a fruitful source of graph-theoretic results.
Drawing graphs
Graphs are represented graphically by drawing a dot for every vertex, and drawing an arc between two vertices if they're connected by an edge. If the graph is directed, the direction is indicated by drawing an arrow.
A graph drawing shouldn't be confused with the graph itself (the abstract, non-graphical structure) as there are several ways to structure the graph drawing. All that matters is which vertices are connected to which others by how many edges and not the exact layout. In practice it's often difficult to decide if two drawings represent the same graph. Depending on the problem domain some layouts may be better suited and easier to understand than others.
Graph-theoretic data structures
There are different ways to store graphs in a computer system. The
data structure used depends on both the graph structure and the
algorithm used for manipulating the graph. Theoretically one can distinguish between list and matrix structures but in concrete applications the best structure is often a combination of both. List structures are often preferred for
sparse graphs as they've smaller memory requirements. Matrix structures on the other hand provide faster access for some applications but can consume huge amounts of memory .
List structures
Incidence list : The edges are represented by an array containing pairs (ordered if directed) of vertices (that the edge connects) and possibly weight and other data. Vertices connected by an edge are said to be adjacent.
; Adjacency list : Much like the incidence list, each vertex has a list of which vertices it's adjacent to. This causes redundancy in an undirected graph: for example, if vertices A and B are adjacent, A's adjacency list contains B, while B's list contains A. Adjacency queries are faster, at the cost of extra storage space.
Matrix structures
Incidence matrix : The graph is represented by a matrix of size |V| (number of vertices) by |E| (number of edges) where the entry [vertex,edge] contains the edge's endpoint data (simplest case: 1 - connected, 0 - not connected).
; Adjacency matrix : This is the n by n matrix A, where n is the number of vertices in the graph. If there's an edge from some vertex x to some vertex y, then the element .
Another class of problems has to do with the extent to which various species and generalizations of graphs are determined by their point-deleted subgraphs, for example:
The reconstruction conjecture
Graph coloring
Many problems have to do with various ways of coloring graphs, for example:
The four-color theorem
The strong perfect graph theorem
The Erdős-Faber-Lovász conjecture (unsolved)
The total coloring conjecture (unsolved)
The list coloring conjecture (unsolved)
Route problems
Hamiltonian path and cycle problems
Minimum spanning tree
Route inspection problem (also called the "Chinese Postman Problem")
Seven Bridges of Königsberg
Shortest path problem
Steiner tree
Three-cottage problem
Traveling salesman problem (NP-complete)
Network flow
There are numerous problems arising especially from applications that have to do with various notions of flows in networks, for example:
Max flow min cut theorem
Visibility graph problems
Museum guard problem
Covering problems
Covering problems are specific instances of subgraph-finding problems, and they tend to be closely related to the clique problem or the independent set problem.
Set cover problem
Vertex cover problem
Applications
Applications of graph theory are primarily, but not exclusively, concerned with labeled graphs and various specializations of these.
Structures that can be represented as graphs are ubiquitous, and many problems of practical interest can be represented by graphs. The link structure of a website could be represented by a directed graph: the vertices are the web pages available at the website and a directed edge from page A to page B exists if and only if A contains a link to B. A similar approach can be taken to problems in travel, biology, computer chip design, and many other fields. The development of algorithms to handle graphs is therefore of major interest in computer science.
A graph structure can be extended by assigning a weight to each edge of the graph. Graphs with weights, or weighted graphs, are used to represent structures in which pairwise connections have some numerical values. For example if a graph represents a road network, the weights could represent the length of each road. A digraph with weighted edges in the context of graph theory is called a network.
Networks have many uses in the practical side of graph theory, network analysis (for example, to model and analyze traffic networks). Within network analysis, the definition of the term "network" varies, and may often refer to a simple graph.
Many applications of graph theory exist in the form of network analysis. These split broadly into three categories. Firstly, analysis to determine structural properties of a network, such as the distribution of vertex degrees and the diameter of the graph. A vast number of graph measures exist, and the production of useful ones for various domains remains an active area of research. Secondly, analysis to find a measurable quantity within the network, for example, for a transportation network, the level of vehicular flow within any portion of it. Thirdly, analysis of dynamical properties of networks.
Graph theory is also used to study molecules in chemistry and physics. In condensed matter physics, the three dimensional structure of complicated simulated atomic structures can be studied quantitatively by gathering statistics on graph-theoretic properties related to the topology of the atoms. For example, Franzblau's shortest-path (SP) rings. In chemistry a graph makes a natural model for a molecule, where vertices represent atoms and edges bonds. This approach is especially used in computer processing of molecular structures, ranging from chemical editors to database searching.
Graph theory is also widely used in sociology as a way, for example, to measure actors' prestige or to explore diffusion mechanisms, notably through the use of social network analysis software.
Further Information
Get more info on 'Graph Theory'.
|
External Link Exchanges
Do you know how hard it is to get a link from a large encyclopaedia? Well we're different and will prove it. To get a link from us just add the following HTML to your site on a relevant page:
<a href="http://graph_theory.totallyexplained.com">Graph theory Totally Explained</a>
Then simply click through this link from your web page. Our crawlers will verify your link, extract the title of your web page and instantly add a link back to it. If you like you can remove the words Totally Explained and embed the link in article text.
As long as your link remains in place, we'll keep our link to you right here. Please play fair - our crawlers are watching. Your site must be closely related to this one's topic. Any kind of spamming, dubious practises or removing the link will result in your link from us being dropped and, potentially, your whole site being banned. |
